// File:       set.c++
// Version:    1.00
// Author:     (c) Miles Sabin, 1997
// Purpose:    approximation to ANSI C++ set and multiset class templates

// Change log:
//  24/01/97   v. 1.00
//  23/02/97   Adapted to HoistHelper/HoistComparator split.
//  01/04/97   Key comparator is now a hoisted binary predicate.
//             Added constructors with comparator arguments.
//  04/04/97   Replaced HoistComparators with HoistBinaryPredicates.

#include "set.h"

#include "hoistbp.h"
#include "hoistctdt.h"
#include "tpltutil.h"


// Implementation of set<Key, Compare>

#define set_type                  set<Key, Compare>
#define key_type                  Key
#define value_type                Key
#define reference                 Key&
#define const_reference           Key const&
#define iterator                  set_iterator<Key, Compare>
#define const_iterator            set_const_iterator<Key, Compare>
#define rev_iterator              reverse_bidirectional_iterator<iterator, value_type, value_type const&>
#define const_rev_iterator        reverse_bidirectional_iterator<const_iterator, value_type, value_type const&>
#define size_type                 size_t
#define difference_type           ptrdiff_t

#ifndef INSTANTIATE_SET_COMPARATORS_ONLY
#ifndef INSTANTIATE_MULTISET_COMPARATORS_ONLY
#ifndef INSTANTIATE_MULTISET_NON_COMPARATORS_ONLY

template<class Key, class Compare>
set<Key, Compare>::set()
  : tree_(get_hoist_constructor_destructor((Key*)0), 0, new HoistBinaryPredicate<Compare, Key>(key_cmp_), false)
  {}

template<class Key, class Compare>
set<Key, Compare>::set(Compare const& cmp)
  : key_cmp_(cmp),
    tree_(get_hoist_constructor_destructor((Key*)0), 0, new HoistBinaryPredicate<Compare, Key>(key_cmp_), false)
  {}

template<class Key, class Compare>
set<Key, Compare>::set(iterator const& first, iterator const& last)
  : tree_(get_hoist_constructor_destructor((Key*)0), 0, new HoistBinaryPredicate<Compare, Key>(key_cmp_), false, first.node_, last.node_)
  {}

template<class Key, class Compare>
set<Key, Compare>::set(iterator const& first, iterator const& last, Compare const& cmp)
  : key_cmp_(cmp),
    tree_(get_hoist_constructor_destructor((Key*)0), 0, new HoistBinaryPredicate<Compare, Key>(key_cmp_), false, first.node_, last.node_)
  {}

template<class Key, class Compare>
set<Key, Compare>::set(value_type const* first, value_type const* last)
  : tree_(get_hoist_constructor_destructor((Key*)0), 0, new HoistBinaryPredicate<Compare, Key>(key_cmp_), false, first, last)
  {}

template<class Key, class Compare>
set<Key, Compare>::set(value_type const* first, value_type const* last, Compare const& cmp)
  : key_cmp_(cmp),
    tree_(get_hoist_constructor_destructor((Key*)0), 0, new HoistBinaryPredicate<Compare, Key>(key_cmp_), false, first, last)
  {}

template<class Key, class Compare>
set<Key, Compare>::set(set<Key, Compare> const& rhs)
  : key_cmp_(rhs.key_cmp_),
    tree_(rhs.tree_, new HoistBinaryPredicate<Compare, Key>(key_cmp_))
  {}

template<class Key, class Compare>
set<Key, Compare>::~set()
  {}

template<class Key, class Compare>
const_iterator set<Key, Compare>::begin() const
  { return const_iterator(&tree_, tree_.begin()); }

template<class Key, class Compare>
const_iterator set<Key, Compare>::end() const
  { return const_iterator(&tree_, tree_.end()); }

template<class Key, class Compare>
const_rev_iterator set<Key, Compare>::rbegin() const
  { return const_rev_iterator(end()); }

template<class Key, class Compare>
const_rev_iterator set<Key, Compare>::rend() const
  { return const_rev_iterator(begin()); }

template<class Key, class Compare>
bool set<Key, Compare>::empty() const
  { return tree_.empty(); }

template<class Key, class Compare>
size_type set<Key, Compare>::size() const
  { return tree_.size(); }

template<class Key, class Compare>
size_type set<Key, Compare>::max_size() const
  { return tree_.max_size(); }

template<class Key, class Compare>
const_iterator set<Key, Compare>::find(key_type const& x) const
  { return const_iterator(&tree_, tree_.find(&x)); }

template<class Key, class Compare>
size_type set<Key, Compare>::count(key_type const& x) const
  { return tree_.count(&x); }

template<class Key, class Compare>
const_iterator set<Key, Compare>::lower_bound(key_type const& x) const
  { return const_iterator(&tree_, tree_.lower_bound(&x)); }

template<class Key, class Compare>
const_iterator set<Key, Compare>::upper_bound(key_type const& x) const
  { return const_iterator(&tree_, tree_.upper_bound(&x)); }

template<class Key, class Compare>
pair<const_iterator, const_iterator> set<Key, Compare>::equal_range(key_type const& x) const
  {
    pair<assoc_base_node const*, assoc_base_node const*> range = tree_.equal_range(&x);
    return make_pair(const_iterator(&tree_, range.first), const_iterator(&tree_, range.second));
  }

template<class Key, class Compare>
Compare set<Key, Compare>::key_compare() const
  { return key_cmp_; }

template<class Key, class Compare>
set<Key, Compare>& set<Key, Compare>::operator=(set<Key, Compare> const& rhs)
  {
    tree_ = rhs.tree_;
    return *this;
  }

template<class Key, class Compare>
iterator set<Key, Compare>::begin()
  { return iterator(&tree_, tree_.begin()); }

template<class Key, class Compare>
iterator set<Key, Compare>::end()
  { return iterator(&tree_, tree_.end()); }

template<class Key, class Compare>
rev_iterator set<Key, Compare>::rbegin()
  { return rev_iterator(end()); }

template<class Key, class Compare>
rev_iterator set<Key, Compare>::rend()
  { return rev_iterator(begin()); }

template<class Key, class Compare>
pair<iterator, bool> set<Key, Compare>::insert(value_type const& x)
  {
    pair<assoc_base_node*, bool> result = tree_.insert(&x);
    return make_pair(iterator(&tree_, result.first), result.second);
  }

template<class Key, class Compare>
iterator set<Key, Compare>::insert(iterator const& hint, value_type const& x)
  { return iterator(&tree_, tree_.insert(const_cast(assoc_base_node*, hint.node_), &x)); }

template<class Key, class Compare>
void set<Key, Compare>::insert(iterator const& first, iterator const& last)
  { tree_.insert(first.node_, last.node_); }

template<class Key, class Compare>
void set<Key, Compare>::insert(value_type const* first, value_type const* last)
  { tree_.insert(first, last); }

template<class Key, class Compare>
void set<Key, Compare>::erase(iterator position)
  { tree_.erase(position.node_); }

template<class Key, class Compare>
size_type set<Key, Compare>::erase(key_type const& x)
  { return tree_.erase(&x); }

template<class Key, class Compare>
void set<Key, Compare>::erase(iterator first, iterator last)
  { tree_.erase(const_cast(assoc_base_node*, first.node_), const_cast(assoc_base_node*, last.node_)); }

template<class Key, class Compare>
void set<Key, Compare>::swap(set<Key, Compare>& x)
  { tree_.swap(x.tree_); }

template<class Key, class Compare>
void set<Key, Compare>::clear()
  { tree_.clear(); }

template<class Key, class Compare>
iterator set<Key, Compare>::find(key_type const& x)
  { return iterator(&tree_, tree_.find(&x)); }

template<class Key, class Compare>
iterator set<Key, Compare>::lower_bound(key_type const& x)
  { return iterator(&tree_, tree_.lower_bound(&x)); }

template<class Key, class Compare>
iterator set<Key, Compare>::upper_bound(key_type const& x)
  { return iterator(&tree_, tree_.upper_bound(&x)); }

template<class Key, class Compare>
pair<iterator, iterator> set<Key, Compare>::equal_range(key_type const& x)
  {
    pair<assoc_base_node*, assoc_base_node*> range = tree_.equal_range(&x);
    return make_pair(iterator(&tree_, range.first), iterator(&tree_, range.second));
  }

#endif
#endif
#endif

#undef set_type
#undef key_type
#undef value_type
#undef reference
#undef const_reference
#undef iterator
#undef const_iterator
#undef rev_iterator
#undef const_rev_iterator
#undef size_type
#undef difference_type


// Implementation of set<Key, Compare> free fns

#ifndef INSTANTIATE_SET_NON_COMPARATORS_ONLY
#ifndef INSTANTIATE_MULTISET_COMPARATORS_ONLY
#ifndef INSTANTIATE_MULTISET_NON_COMPARATORS_ONLY

template<class Key, class Compare>
bool operator==(set<Key, Compare> const& x, set<Key, Compare> const& y)
{
  return x.tree_.is_equal(get_hoist_equal_to_comparator((Key*)0), 0, y.tree_);
}

template<class Key, class Compare>
bool operator< (set<Key, Compare> const& x, set<Key, Compare> const& y)
{
  return x.tree_.is_less_than(get_hoist_less_comparator((Key*)0), 0, y.tree_);
}

#endif
#endif
#endif

// Implementation of set_const_iterator

#ifndef INSTANTIATE_SET_COMPARATORS_ONLY
#ifndef INSTANTIATE_MULTISET_COMPARATORS_ONLY

template<class Key, class Compare>
set_const_iterator<Key, Compare>::set_const_iterator(set_const_iterator<Key, Compare> const& rhs)
  : tree_(rhs.tree_),
    node_(rhs.node_)
  {}

template<class Key, class Compare>
set_const_iterator<Key, Compare>& set_const_iterator<Key, Compare>::operator=(set_const_iterator<Key, Compare> const& rhs)
  {
    tree_ = rhs.tree_;
    node_ = rhs.node_;
    return *this;
  }

template<class Key, class Compare>
set_const_iterator<Key, Compare>& set_const_iterator<Key, Compare>::operator++()
  {
    node_ = tree_->successor(node_);
    return *this;
  }

template<class Key, class Compare>
set_const_iterator<Key, Compare> set_const_iterator<Key, Compare>::operator++(int)
  {
    set_const_iterator<Key, Compare> tmp = *this;
    node_ = tree_->successor(node_);
    return tmp;
  }

template<class Key, class Compare>
set_const_iterator<Key, Compare>& set_const_iterator<Key, Compare>::operator--()
  {
    node_ = tree_->predecessor(node_);
    return *this;
  }

template<class Key, class Compare>
set_const_iterator<Key, Compare> set_const_iterator<Key, Compare>::operator--(int)
  {
    set_const_iterator<Key, Compare> tmp = *this;
    node_ = tree_->predecessor(node_);
    return tmp;
  }

#endif
#endif


// Implementation of multiset<Key, Compare>

#define multiset_type             multiset<Key, Compare>
#define key_type                  Key
#define value_type                Key
#define reference                 Key&
#define const_reference           Key const&
#define iterator                  multiset_iterator<Key, Compare>
#define const_iterator            multiset_const_iterator<Key, Compare>
#define rev_iterator              reverse_bidirectional_iterator<iterator, value_type, value_type const&>
#define const_rev_iterator        reverse_bidirectional_iterator<const_iterator, value_type, value_type const&>
#define size_type                 size_t
#define difference_type           ptrdiff_t

#ifndef INSTANTIATE_MULTISET_COMPARATORS_ONLY
#ifndef INSTANTIATE_SET_COMPARATORS_ONLY
#ifndef INSTANTIATE_SET_NON_COMPARATORS_ONLY

template<class Key, class Compare>
multiset<Key, Compare>::multiset()
  : tree_(get_hoist_constructor_destructor((Key*)0), 0, new HoistBinaryPredicate<Compare, Key>(key_cmp_), true)
  {}

template<class Key, class Compare>
multiset<Key, Compare>::multiset(Compare const& cmp)
  : key_cmp_(cmp),
    tree_(get_hoist_constructor_destructor((Key*)0), 0, new HoistBinaryPredicate<Compare, Key>(key_cmp_), true)
  {}

template<class Key, class Compare>
multiset<Key, Compare>::multiset(iterator const& first, iterator const& last)
  : tree_(get_hoist_constructor_destructor((Key*)0), 0, new HoistBinaryPredicate<Compare, Key>(key_cmp_), true, first.node_, last.node_)
  {}

template<class Key, class Compare>
multiset<Key, Compare>::multiset(iterator const& first, iterator const& last, Compare const& cmp)
  : key_cmp_(cmp),
    tree_(get_hoist_constructor_destructor((Key*)0), 0, new HoistBinaryPredicate<Compare, Key>(key_cmp_), true, first.node_, last.node_)
  {}

template<class Key, class Compare>
multiset<Key, Compare>::multiset(value_type const* first, value_type const* last)
  : tree_(get_hoist_constructor_destructor((Key*)0), 0, new HoistBinaryPredicate<Compare, Key>(key_cmp_), true, first, last)
  {}

template<class Key, class Compare>
multiset<Key, Compare>::multiset(value_type const* first, value_type const* last, Compare const& cmp)
  : key_cmp_(cmp),
    tree_(get_hoist_constructor_destructor((Key*)0), 0, new HoistBinaryPredicate<Compare, Key>(key_cmp_), true, first, last)
  {}

template<class Key, class Compare>
multiset<Key, Compare>::multiset(multiset<Key, Compare> const& rhs)
  : key_cmp_(rhs.key_cmp_),
    tree_(rhs.tree_, new HoistBinaryPredicate<Compare, Key>(key_cmp_))
  {}

template<class Key, class Compare>
multiset<Key, Compare>::~multiset()
  {}

template<class Key, class Compare>
const_iterator multiset<Key, Compare>::begin() const
  { return const_iterator(&tree_, tree_.begin()); }

template<class Key, class Compare>
const_iterator multiset<Key, Compare>::end() const
  { return const_iterator(&tree_, tree_.end()); }

template<class Key, class Compare>
const_rev_iterator multiset<Key, Compare>::rbegin() const
  { return const_rev_iterator(end()); }

template<class Key, class Compare>
const_rev_iterator multiset<Key, Compare>::rend() const
  { return const_rev_iterator(begin()); }

template<class Key, class Compare>
bool multiset<Key, Compare>::empty() const
  { return tree_.empty(); }

template<class Key, class Compare>
size_type multiset<Key, Compare>::size() const
  { return tree_.size(); }

template<class Key, class Compare>
size_type multiset<Key, Compare>::max_size() const
  { return tree_.max_size(); }

template<class Key, class Compare>
const_iterator multiset<Key, Compare>::find(key_type const& x) const
  { return const_iterator(&tree_, tree_.find(&x)); }

template<class Key, class Compare>
size_type multiset<Key, Compare>::count(key_type const& x) const
  { return tree_.count(&x); }

template<class Key, class Compare>
const_iterator multiset<Key, Compare>::lower_bound(key_type const& x) const
  { return const_iterator(&tree_, tree_.lower_bound(&x)); }

template<class Key, class Compare>
const_iterator multiset<Key, Compare>::upper_bound(key_type const& x) const
  { return const_iterator(&tree_, tree_.upper_bound(&x)); }

template<class Key, class Compare>
pair<const_iterator, const_iterator> multiset<Key, Compare>::equal_range(key_type const& x) const
  {
    pair<assoc_base_node const*, assoc_base_node const*> range = tree_.equal_range(&x);
    return make_pair(const_iterator(&tree_, range.first), const_iterator(&tree_, range.second));
  }

template<class Key, class Compare>
Compare multiset<Key, Compare>::key_compare() const
  { return key_cmp_; }

template<class Key, class Compare>
multiset<Key, Compare>& multiset<Key, Compare>::operator=(multiset<Key, Compare> const& rhs)
  {
    tree_ = rhs.tree_;
    return *this;
  }

template<class Key, class Compare>
iterator multiset<Key, Compare>::begin()
  { return iterator(&tree_, tree_.begin()); }

template<class Key, class Compare>
iterator multiset<Key, Compare>::end()
  { return iterator(&tree_, tree_.end()); }

template<class Key, class Compare>
rev_iterator multiset<Key, Compare>::rbegin()
  { return rev_iterator(end()); }

template<class Key, class Compare>
rev_iterator multiset<Key, Compare>::rend()
  { return rev_iterator(begin()); }

template<class Key, class Compare>
pair<iterator, bool> multiset<Key, Compare>::insert(value_type const& x)
  {
    pair<assoc_base_node*, bool> result = tree_.insert(&x);
    return make_pair(iterator(&tree_, result.first), result.second);
  }

template<class Key, class Compare>
iterator multiset<Key, Compare>::insert(iterator const& hint, value_type const& x)
  { return iterator(&tree_, tree_.insert(const_cast(assoc_base_node*, hint.node_), &x)); }

template<class Key, class Compare>
void multiset<Key, Compare>::insert(iterator const& first, iterator const& last)
  { tree_.insert(first.node_, last.node_); }

template<class Key, class Compare>
void multiset<Key, Compare>::insert(value_type const* first, value_type const* last)
  { tree_.insert(first, last); }

template<class Key, class Compare>
void multiset<Key, Compare>::erase(iterator position)
  { tree_.erase(position.node_); }

template<class Key, class Compare>
size_type multiset<Key, Compare>::erase(key_type const& x)
  { return tree_.erase(&x); }

template<class Key, class Compare>
void multiset<Key, Compare>::erase(iterator first, iterator last)
  { tree_.erase(const_cast(assoc_base_node*, first.node_), const_cast(assoc_base_node*, last.node_)); }

template<class Key, class Compare>
void multiset<Key, Compare>::swap(multiset<Key, Compare>& x)
  { tree_.swap(x.tree_); }

template<class Key, class Compare>
void multiset<Key, Compare>::clear()
  { tree_.clear(); }

template<class Key, class Compare>
iterator multiset<Key, Compare>::find(key_type const& x)
  { return iterator(&tree_, tree_.find(&x)); }

template<class Key, class Compare>
iterator multiset<Key, Compare>::lower_bound(key_type const& x)
  { return iterator(&tree_, tree_.lower_bound(&x)); }

template<class Key, class Compare>
iterator multiset<Key, Compare>::upper_bound(key_type const& x)
  { return iterator(&tree_, tree_.upper_bound(&x)); }

template<class Key, class Compare>
pair<iterator, iterator> multiset<Key, Compare>::equal_range(key_type const& x)
  {
    pair<assoc_base_node*, assoc_base_node*> range = tree_.equal_range(&x);
    return make_pair(iterator(&tree_, range.first), iterator(&tree_, range.second));
  }

#endif
#endif
#endif

#undef multiset_type
#undef key_type
#undef value_type
#undef reference
#undef const_reference
#undef iterator
#undef const_iterator
#undef rev_iterator
#undef const_rev_iterator
#undef size_type
#undef difference_type

// Implementation of multiset<Key, Compare> free fns

#ifndef INSTANTIATE_MULTISET_NON_COMPARATORS_ONLY
#ifndef INSTANTIATE_SET_COMPARATORS_ONLY
#ifndef INSTANTIATE_SET_NON_COMPARATORS_ONLY

template<class Key, class Compare>
bool operator==(multiset<Key, Compare> const& x, multiset<Key, Compare> const& y)
{
  return x.tree_.is_equal(get_hoist_equal_to_comparator((Key*)0), 0, y.tree_);
}

template<class Key, class Compare>
bool operator< (multiset<Key, Compare> const& x, multiset<Key, Compare> const& y)
{
  return x.tree_.is_less_than(get_hoist_less_comparator((Key*)0), 0, y.tree_);
}

#endif
#endif
#endif
